# -*- coding: utf-8 -*- 
# @project : 《剑指offer》
# @Author : created by bensonrachel on 2021/6/11
# @File : 剪绳子DP方法.py

import math
class Solution(object):
    def maxProductAfterCutting(self,length):#DP
        """
        :type length: int
        :rtype: int
        """
        dp=[1]*(length+1)
        for i in range(2,length+1):#dp[i]表示长度为i的绳子剪成m段后的最大乘积
            for j in range(2,i):#(2,i)or(1,i//2+1)都行
                dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]))
        return dp[length]
if __name__ == '__main__':
    a = Solution()
    b = a.maxProductAfterCutting(3)
    print(b)